package treeNode;

import java.util.LinkedList;
import java.util.List;

//后序遍历

/**
 * 首先遍历左子树，然后遍历右子树，最后访问根结点，
 * 在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。
 */
public class Solution12I {

    //迭代方法:利用pre记录上一个访问过的结点，与当前结点比较，
    // 如果是当前结点的子节点，说明其左右结点均已访问，将当前结点出栈，更新pre记录的对象。
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> res = new LinkedList<Integer>(); //结果
        if(root==null){
            return res;
        }
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); //栈，存放没有统计结果的node，统计了结果就pop出处
        stack.push(root);
        TreeNode node = root;
        TreeNode pre = null; //记录上一个访问过的结点，与当前结点比较
        while(!stack.isEmpty()){
            TreeNode currNode = stack.peek(); //Retrieves, but does not remove
            //栈里面的当前节点
            if((currNode.left==null&&currNode.right==null)//当前节点为叶节点
                ||( (pre!=null)&&(currNode.left==pre||currNode.right==pre) ) //当前节点的左或右节点已经访问过
                    ){
                res.add(currNode.val);
                pre=currNode;
                stack.pop();
            }else{
                if(currNode.right!=null){
                    stack.push(currNode.right);
                }
                if(currNode.left!=null){
                    stack.push(currNode.left);
                }

            }

        }





        return res;
    }


    public static void main(String[] args) {
        /**
         *                 1
         *              /     \
         *             2            3
         *            / \        /      \
         *          4   5       6       7
         *       / \   / \     / \     /  \
         *      8  9  10  11  12  13  14   15
         */
        TreeNode root = TreeNodeUtils.getTestTreeNode();
        Solution12I solution = new Solution12I();
        System.out.println(solution.postorderTraversal(root));


    }


}
